1. Field of the Invention
The present invention relates to a redundant binary code conversion circuit and a multiplication circuit in which the same is used.
2. Description of the Related Art
FIG. 11 shows a brief configuration of a prior art multiplication circuit.
It is assumed that a multiplicand and multiplier are a positive integer of n bits. Furthermore, it is assumed that each of register 10 and higher-order bit part 11H and lower-order bit part 11L of shift register 11 is of n bits. In the drawing, C is a count of counter 13 and CO is a carry output from adder circuit 14. The following processes are carried out by control circuit 12.
(1) A multiplicand is loaded in register 10, a multiplier is loaded in lower-order bit part 11L of shift register 11, and higher-order bit part 11H of shift register 11 is cleared to be zero. Initial-value n is loaded in counter 13.
(2) With CO provided in the MSB of shift register 11, shift register 11 is shifted by one bit in the direction of the arrow.
(3) If the shifted output bit from the LSB of shift register 11 is `1`, (Higher-order bit part 11H).rarw.(Higher-order bit part 11H)+(Register 10), and if the bit is `0`, the process is skipped.
(4) C.rarw.C-1
(5) If C=0, the process ends, and if C.noteq.0, the process returns to step (2).
Although the construction of this multiplication circuit is simple, the calculation time is lengthened since addition and shift processes are repeatedly carried out. This problem will become remarkable with an increase of the number of digits, wherein the process rate such as DSP equipped with a multiplication circuit is greatly influenced by the calculation rate of the multiplication circuit. Especially, in DSP which is used for a portable telephone, image processing device, etc., a fast process is requested.
From the above-mentioned (3), the more the number of zeros which are included in multiplier becomes, the more the time of multiplication is decreased.
On the other hand, according to RBC (redundant binary code) of ternary code, it can be converted to a code of the same value including more zeros by utilizing its redundancy. The RBC n digits of a number Z is ##EQU1## where .alpha.i.epsilon.{1, 0, -1} and this number Z is expressed in vector notation as EQU Z=`.alpha.n-1.alpha.n-2....alpha.2.alpha.1.alpha.0`.
Usual binary codes are included in RBCs of ternary code. For example, RBC `01111111` can be converted to RBC `01000000T`, where T represents -1. A.times.`1000000T` needs only the calculation of the above step (3) only two times while A.times.`01111111` needs calculations of the step (3) seven times.
Therefore, in FIG. 11, an RBC multiplier is loaded in register 15, the multiplier is converted in RBC conversion circuit 16 to increase the number of zeros, and the same is loaded in the lower-order bit part 11L of shift register 11. The process in RBC conversion circuit 16 can be carried out in parallel with the previous multiplication.
In such an RBC multiplication circuit, the output of RBC conversion circuit 16, the lower-order bit part 11L and higher-order bit part 11H are of n digits of RBC. Further, registers 10 and 15 are of n digits of RBC, and adder- subtracter circuit 14 is for addition or subtraction between a RBC n digits and another RBC n digits.
In the prior art, code conversion is carried out by RBC conversion circuit 16 on the basis of the following truth TABLE I.
TABLE I ______________________________________ INPUT OUTPUT No. X.sub.i+1 X.sub.i X.sub.i-1 X.sub.i-2 Y.sub.i ______________________________________ 1 1 1 0 2 1or1 1 0 1 3 1 1 0 4 0 1 1 1 5 0 1 1 1 6 1 1 0 7 1or1 1 0 1 8 1 1 0 ______________________________________
Values at the blank on TABLE I are don't care. Furthermore, 1 with a top bar is equal to -1 (T), and rows No. 1 through No. 4 are complementary with rows No. 8 through 5, respectively.
Generally converted value Yi of the ith digit is defined by pre-conversion values Xi+1 through Xi-2 of the (i-1)th through (i-2)th digits. For example, `X4X3X2X1X0`-`01111` coverted to `Y4Y3Y2Y1Y0` as described below with Xj=0 for j=-2, -1 and 5 which do not exist.
For i-0 as input is `1100`, row No. 7 in Table is applied, then Y0=`T`.
For i=1; as input is `1110`, row No. 8 in Table is applied, then Y1-`0`.
For i=2; as input is `1111`, row No. 8 in Table is applied, then Y2=`0`.
For i=3; as input is `0111`, row No. 8 in Table is applied, then Y3=`0`.
For i=4; as input is `0011`, row No. 5 in Table is applied, then Y4=`1`.
Thus, RBC `01111` is converted to RBC `1000T`. These processes of i=0 through 4 can be carried out in parallel to one another.
However, the number m of zeros included in the converted RBC differs in compliance with the numerals of pre-conversion, and in design, the slowest multiplication speed with m at the minimum must be used. This problem will become remarkable with an increase of the digit number according to a high performance tendency of DSP, etc. in which a multiplication circuit is used.